A continuación se presentan los resultados experimentales efectuados
sobre distintas instancias de problemas de clasificación usando clustering
con las metaheurísticas planteadas. Dado que los resultados para las
metaheurísticas de trayectoria no son comparables con los resultados
de las constructivas, estos son presentados por separado.

Las instancias iniciales para las metaheurísticas de trayectoria fueron
construidas con un método aleatorio, no
se utilizó ninguna solución voraz determinística para favorecer así la
diversificación como resultado de múltiples ejecuciones.

Los siguientes experimentos fueron ejecutados en un computador con procesador
Intel Core2Duo 2.4, con 4 Gb de memoria RAM, sin embargo, los experimentos
no consumieron grandes cantidades de memoria por tratarse de simples
metaheurísticas de trayectoria, donde se necesitan mantener pocos estados
a la vez en memoria.

Los valores asignados a los parámetros correspondientes son:

\begin{center}
	\begin{tabular}{|c|c|}
		\hline
		\textbf{Parámetro} & \textbf{Valor}\\
		\hline
		Número de Iteraciones (Trayectoria) & 1000\\
		\hline
		Número de Iteraciones (Constructiva) & 400000\\
		\hline
		Número Máximo de Élites (TS) & 10\\
		\hline
		Tamaño memoria a corto plazo (TS) & 150\\
		\hline
		Número de hormigas & 20\\
		\hline
		q (Probabilidad de destruir un cluster binario) & 0.7\\
		\hline
	\end{tabular}
\end{center}

Cada uno de los casos fue ejecutado treinta (30) veces con cada
metaheurística.

\subsection{Problemas Estudiados}

Se estudió un total de cuatro tipos de problemas, tres con instancias
únicas y uno último con múltiples instancias. A continuación se presenta
la definición de los problemas estudiados.

\subsubsection{Iris}

Este problema es el más común en la literatura de reconocimiento de patrones.
Consiste en la clasificación de plantas de lirios según su clase, el problema
cuenta con tres clases, cada una con 50 instancias.

En el problema original, existe una clase linearmente separable de las otras dos,
en cambio, las otras no son separables linealmente entre si. En los resultados,
observamos cómo las distintas metaheurísticas lograron clasificar correctamente
las instancias de la primera clases, mientras que en las otras dos clases ocurrían
errores de clasificación.

Los atributos dados por cada instancia de planta son el tamaño del sépalo y los
pétalos en largo y ancho.

\subsubsection{Wine}

En este caso, se busca clasificar vinos según tres distintas clases, para esto,
contamos con 178 instancias, cada una con 13 atributos cuya semántica es el
grado de cada constituyente en el vino.

Al igual que el problema anterior, este caso es clásico en el área de clasificación.

\subsubsection{Ecoli}

Este conjunto de datos está constuido por 336 instancias con 7 atributos cada
uno. Con los datos, se busca predecir el lugar donde se localiza una determinada
proteina, la localización, esto puede ser en un total de 8 lugares, con lo cual
estamos buscando una partición en clusters de tamaño 8.

\subsubsection{Círculos}

Este problema se trata de un conjunto propio de pruebas, se busca generar puntos
en el plano cartesiano $\mathbb{R}^2$, cada punto se encuentra dentro de un
determinado círculo, se busca una distribución uniforme de los puntos en el
círculo.

El valor a predecir es a qué círculo pertenece cada punto. Si bien este parece ser
un problema sencillo de clasificación, es útil para determinar gráficamente la
bondad de las metaheurísticas.

En los casos de prueba, las instancias presentadas se denotan como $ci$ donde, $i$
está comprendida en el intervalo $[1..6]$, las primeras tres instancias se
deben ejecutar con 4 clusters y las últimas 3 con 7 clusters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Resultados de las Metaheurísticas de Trayectoria}

\subsubsection{Resultados de la Metaheurística Local Search}

\input{tables/tablasLS}

\input{tables/tablas2LS}

\input{tables/tablas3LS}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Resultados de la Metaheurística Iterated Local Search}

\input{tables/tablasILS}

\input{tables/tablas2ILS}

\input{tables/tablas3ILS}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Resultados de la Metaheurística Tabu Search}

\input{tables/tablasTS}

\input{tables/tablas2TS}

\input{tables/tablas3TS}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Resultados de la Metaheurística Variable Neighborhood Search}

\input{tables/tablasVNS}

\input{tables/tablas2VNS}

\input{tables/tablas3VNS}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Resultados Globales}

A continuación se presenta las tablas de resultados globales para
cada problema usando metaheurísticas de trayectoria. Se señalan en
negritas los mejores resultados de cada campo, es decir, qué
metaheurística tuvo los mejores resultados en los estudios de bondad
mejor, peor y promedio de los clusters.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Iris}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.3173 & 0.1297 & 0.2526 & 0.0132 & 2.43\\
\hline
ILS & 0.2977 & \textbf{0.1129} & 0.1981 & 0.1394 & 1000.0\\
\hline
TS & \textbf{0.2545} & 0.1332 & \textbf{0.1962} & 10.0239 & 19.0\\
\hline
VNS & 0.3074 & 0.138 & 0.242 & 0.0115 & 2.47\\
\hline
\multicolumn{6}{|c|}{\textbf{Wine}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.462 & 0.391 & 0.4504 & 0.0124 & 3.2\\
\hline
ILS & 0.4634 & \textbf{0.2967} & 0.4167 & 0.5884 & 1000.0\\
\hline
TS & \textbf{0.4291} & 0.3391 & \textbf{0.3751} & 10.0722 & 19.0\\
\hline
VNS & 0.4634 & 0.36 & 0.4359 & 0.012 & 3.17\\
\hline
\multicolumn{6}{|c|}{\textbf{Ecoli}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2197 & 0.161 & 0.186 & 0.0187 & 5.7 \\
\hline
ILS & 0.2193 & \textbf{0.1359} & 0.1854 & 1.334 & 1000.0 \\
\hline
TS & \textbf{0.1943} & 0.157 & \textbf{0.1724} & 10.1643 & 19.0 \\
\hline
VNS & 0.2105 & 0.1547 & 0.1803 & 0.0199 & 6.07 \\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 1}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2497 & 0.0886 & 0.1606 & 0.0342 & 2.67\\
\hline
ILS & 0.231 & \textbf{0.0738} & 0.1328 & 0.5955 & 1000.0 \\
\hline
TS & \textbf{0.1239} & 0.0873 & \textbf{0.0946} & 10.0901 & 19.0\\
\hline
VNS &  0.2304 & 0.0886 & 0.1359 & 0.0281 & 3.23\\
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 2}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2554 & 0.0948 & 0.1097 & 0.028 & 2.8\\
\hline
ILS & 0.2973 & \textbf{0.0527} & 0.1073 & 0.701 & 1000.0\\
\hline
TS & \textbf{0.1114} & 0.0916 & \textbf{0.0952} & 10.0836 & 19.0\\
\hline
VNS & 0.2535 & 0.0948 & 0.1064 & 0.0222 & 2.77\\
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 3}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2835 & 0.0746 & 0.1101 & 0.0287 & 2.83 \\
\hline
ILS & 0.3001 & \textbf{0.0293} & 0.1033 & 0.7245 & 1000.0 \\
\hline
TS & \textbf{0.0746} & 0.0731 & \textbf{0.0745} & 10.0871 & 19.0 \\
\hline
VNS & 0.2486 & 0.0746 & 0.0865 & 0.0227 & 2.9 \\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 4}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.1962 & 0.0545 & 0.1405 & 0.0562 & 4.2\\
\hline
ILS & 0.1895 & 0.0545 & 0.1242 & 1.9969 & 1000.0\\
\hline
TS & \textbf{0.1611} & \textbf{0.045} & \textbf{0.1005} & 10.2218 & 19.0\\
\hline
VNS & 0.1795 & 0.0545 & 0.1236 & 0.0609 & 4.0\\
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 5}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.152 & 0.0783 & 0.1169 & 0.0548 & 3.2\\
\hline
ILS & \textbf{0.1402} & 0.0783 & 0.1091 & 1.9318 & 1000.0\\
\hline
TS & \textbf{0.1402} & 0.0783 & \textbf{0.1018} & 10.1956 & 19.0\\
\hline
VNS & 0.1403 & \textbf{0.0782} & 0.1129 & 0.0526 & 4.07\\
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 6}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.1712 & 0.0906 & \textbf{0.1136} & 0.054 & 4.1\\
\hline
ILS & 0.1664 & 0.0906 & 0.1358 & 2.1301 & 1000.0\\
\hline
TS & \textbf{0.1639} & \textbf{0.0874} & 0.1196 & 10.2235 & 19.0 \\
\hline
VNS & 0.1712 & 0.0905 & 0.1282 & 0.0606 & 4.47 \\
\hline
\end{tabular}
\end{center}

\subsubsection{Análisis de Resultados}

Como podemos observar en las tablas globales, los peores casos de
\textit{Tabu Search} (TS) son de mayor calidad que los peores casos de las
demás metaheurísticas propuestas, por lo tanto, podemos asegurar que
este es más confiable.

A su vez, en el caso promedio, TS se comportó mejor que las demás
metaheurísticas en la mayoría de los casos, exceptuando los casos
de círculos 5 y 6 donde se comportaron en promedio mejor \textit{Local Search}
y \textit{Variable Neighborhood Search} respectivamente.

Por lo tanto, en la mayoría de los casos TS se comportó mejor en el
caso promedio y en el peor de los casos al compararse contra las otras
metaheurísticas en los problemas estudiados.

Sin embargo, en la mayoría de los casos, la mejor solución encontrada
vino dada por la metaheurística \textit{Iterated Local Search} (ILS),
aún cuando esta en el caso promedio brinda clusters de peor calidad
que TS.

Debemos recordar que todas estas metaheurísticas fueron combinadas con
el algoritmo \textit{k-means} para intensificar las soluciones obtenidas
por las distintas metaheurísticas, por lo tanto, debemos ver, bajo estos
experimentos, todas las metaheurísticas propuestas como un método de
generación de buenas soluciones iniciales para este algoritmo.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Resultados de las Metaheurísticas Constructivas}

\subsubsection{Resultados de la Metaheurística AntClust Algorithm}

\begin{center}
\input{tables2/tablasACA}

\input{tables2/tablasACA2}

\input{tables2/tablasACA3}

\input{tables2/tablasACA4}

\input{tables2/tablasACA5}
\end{center}

\subsubsection{Resultados de la Metaheurística AntClust Hybrid Algorithm}

\begin{center}
\input{tables2/tablasACHA}

\input{tables2/tablasACHA2}

\input{tables2/tablasACHA3}

\input{tables2/tablasACHA4}

\input{tables2/tablasACHA5}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Resultados Globales}

A continuación se presenta las tablas de resultados globales para
cada problema usando metaheurísticas de constructivas. Análogamente,
se señalan en negritas los mejores resultados de cada campo.

\hspace{-0.5cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\textbf{Iris}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2545} & \textbf{0.1143} & \textbf{0.1762} & 4.1975 & \textbf{10} & \textbf{3} & 6.7\\
\hline
ACHA & \textbf{0.2545} & 0.1181 & 0.1964 & 5.4723 & \textbf{10} & \textbf{3} & \textbf{5.03}\\
\hline
\multicolumn{8}{|c|}{\textbf{Wine}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2549} & \textbf{0.1244} & \textbf{0.1734} & 4.3743 & \textbf{13} & \textbf{8} & 11.07\\
\hline
ACHA & 0.2256 & 0.1344 & 0.1735 & 17.2653 & \textbf{13} & \textbf{8} & \textbf{10.83}\\
\hline
\multicolumn{8}{|c|}{\textbf{Ecoli}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.0921 & \textbf{0.0601} & 0.07773 & 4.2162 & 26 & 19 & 20.87\\
\hline
ACHA & \textbf{0.0899} & \textbf{0.0601} & \textbf{0.0729} & 24.5656 &  \textbf{23} & \textbf{17} & \textbf{20.8}\\
\hline
\end{tabular}

\hspace{-0.5cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 1}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2066} & \textbf{0.1023} & \textbf{0.1478} & 4.2262 & 10 & \textbf{3} & 5.9\\
\hline
ACHA & 0.2292 & 0.1181 & 0.1523 & 8.1231 & \textbf{7} & \textbf{3} & \textbf{4.2}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 2}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.2924 & 0.0797 & 0.1382 & 4.3815 & 14 & 4 & 7.13\\
\hline
ACHA & \textbf{0.2423} & \textbf{0.0753} & \textbf{0.1334} & 10.1122 & \textbf{11} & \textbf{3} & \textbf{6.1}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 3}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.1954 & 0.0746 & 0.1149 & 4.4118 & \textbf{12} & \textbf{4} & 7.15\\
\hline
ACHA & \textbf{0.1852} & \textbf{0.0605} & \textbf{0.1146} & 10.95 & 14 & \textbf{4} & \textbf{6.67}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 4}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.209} & \textbf{0.063} & \textbf{0.1237} & 4.473 & 10 & 4 & 6.57\\
\hline
ACHA & 0.3292 & \textbf{0.063} & 0.1276 & 12.0905 & \textbf{8} & \textbf{3} & \textbf{5.37}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 5}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.0818 & 0.0292 & 0.0394 & 5.7047 & \textbf{34} & \textbf{13} & 26.73\\
\hline
ACHA & \textbf{0.0774} & \textbf{0.0202} & \textbf{0.0387} & 44.36 & 51 & \textbf{13} & \textbf{26.87}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 6}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.0777} & 0.0293 & \textbf{0.0468} & 5.528 & \textbf{34} & 13 & 24.97\\
\hline
ACHA & 0.0894 & \textbf{0.0292} & 0.0494 & 40.3574 & 35 & \textbf{12} & \textbf{22.73}\\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Análisis de Resultados}

Para estos casos, no debemos basarnos únicamente en los mejores
resultados en cuanto a nivel de bondad de una agrupación se refiere.
Nótese que la métrica Davies-Bouldin, al tener un mayor número
de clusters, tiende a cero. Por lo tanto, no es comparable un
resultado de una agrupación de $i$ clusters con uno de $j$ si
$i$ es distinto de $j$.

Sin embargo, si deseamos minimizar esta métrica, la metaheurística
que arrojó mejores resultados para los casos \textit{Iris}, \textit{Wine}
y \textit{Ecoli} fue la metaheurística base \textit{AntClust Algorithm}
(ACA). Para los casos de círculos, las metaheurísticas varían en su
mejor resultado, tendiendo la híbrida ACHA a ser mejor.

\bigskip
Por otro lado, podríamos estar interesados en obtener agrupaciones
con un bajo número de clusters. Si este es el caso, se ha observado
que en la gran mayoría de los casos, la metaheurística híbrida ACHA
tiende a conseguir agrupaciones con menos conjuntos. Nótese que al
tener menos conjuntos, el valor de la métrica tiende a ser mayor,
por lo que posiblemente estos conjuntos sean de mayor calidad que
aquellos obtenidos por la metaheurística ACA y que reflejan una mayor
bondad.

\bigskip
Finalmente, dado que la metaheurística ACHA encuentra agrupaciones
con un menor número de clusters de la mano de una pérdida en el valor
de bondad del cluster pequeño, se considera la metaheurística híbrida
como la mejor estudiada.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Soluciones Gráficas Obtenidas}

A continuación, se presentan datos de puntos ubicados en círculos correspondientes
a instancias del problema de \textit{Círculos} presentado anteriormente. Los colores
representan a qué cluster asoció la metaheurística a un punto.

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ls1.jpg}
\caption{LS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ls2.jpg}
\caption{LS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ils1.jpg}
\caption{ILS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ils2.jpg}
\caption{ILS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ts1.jpg}
\caption{TS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ts2.jpg}
\caption{TS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/ts3.jpg}
\caption{TS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/vns1.jpg}
\caption{VNS}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/aca1.jpg}
\caption{ACA}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/aca2.jpg}
\caption{ACA}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/aca3.jpg}
\caption{ACA}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/acha1.jpg}
\caption{ACHA}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/acha2.jpg}
\caption{ACHA}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[H]
\centering
\includegraphics[scale=0.25]{graphics/acha3.jpg}
\caption{ACHA}
\end{figure}
\end{center}